插入排序法(Insertion Sort)，原理是逐一將原始資料加入已排序好資料中，並逐一與已排序好的資料作比較，找到對的位置插入。例如:已有2筆排序好資料，將第3筆資料與前面已排序好的2筆資料作比較，找到對的位置插入，再將第4筆資料與前面已排序好的3筆資料作比較，找到對的位置插入，以此類推。

下面利用40 30 60 50 20由小到大排序。

n=5
第2回合與1個數比較，比1次，n-4次
第3回合在2個數比較，比2次，n-3次
第3回合在2個數比較，比3次，n-2次
第4回合在1個數比較，比4次，n-1次

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均時間複雜度為: O(n²)

JavaScript

let data = [8,6,10,5,3,9,2,7,4,1]

function InsertSort(array) {
  for (let i = 1; i < array.length; i++) {
    let target = i; 
    for (let j = i - 1; j >= 0; j--) {
      if (array[target] < array[j]) {
        [array[target], array[j]] = [array[j], array[target]]
        target = j;
      } 
    }
  }
  return array;
}
console.log(InsertSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

#Insertion Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def InsertionSort(data):
    n = len(data)
    for i in range(n-1):
        key = data[i+1]
        j = i
        while j >=0 and key < data[j] :
                data[j+1] = data[j]
                j -= 1
        data[j+1] = key
    return data
        
print(InsertionSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]